public class TestHeap {
    private int[] elem;
    public  int usedSize;
  public TestHeap(){
      this.elem=new  int[10];
  }
  //初始化
    public void initElem(int[] array){
        for (int i = 0; i <array.length; i++) {
            elem[i]=array[i];
            usedSize++;
        }
    }
   public void createHeap(){
       for (int parent = (usedSize-1-1)/2; parent >=0; parent--) {
                siftDown(parent,usedSize);
       }
   }
   // 其作用是确保以parent为索引的节点及其子节点满足二叉堆性质（即父节点大于或等于其子节点）
   private void siftDown(int parent,int len){
      int child=2*parent+1;
      while (child<len){
          if (child+1<len&&elem[child]<elem[child+1]){
              child=child+1;
          }
          if (elem[child]>elem[parent]){
              swap(child,parent);
              parent=child;
              child=2*parent+1;
          }
          else {
              break;
          }

      }
   }
   private void swap(int i,int j){
      int tmp =elem[i];
      elem[i]=elem[j];
      elem[j]=tmp;
   }
    public boolean isFull() {
        return usedSize == elem.length;
    }
    //其作用是确保以child为索引的节点及其父节点满足二叉堆性质（即父节点大于或等于其子节点）。
    public void siftUp(int child) {
        int parent = (child-1)/2;
        while (child > 0) {
            if (elem[child] > elem[parent]) {
                swap(child, parent);
                child = parent;
                parent = (child - 1) / 2;
            } else {
                break;
            }
        }
    }
    //，其作用是从堆顶弹出（删除并返回）最大值（对于最大堆）或最小值（对于最小堆）
    public int pop() {
        //判空
        if(empty()) {
            return -1;
        }
        int oldVal = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        siftDown(0,usedSize);
        return oldVal;
    }

    public boolean empty() {
        return usedSize == 0;
    }
//排序
    public void heapSort() {
        int end = usedSize-1;
        while (end > 0) {
            swap(0,end);
            siftDown(0,end);
            end--;
        }
    }
}


